import javax.swing.tree.TreeNode;
import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

public class Test {
}
class Solution {

    int ans = 0;
    Map<Integer, Stack<Integer>> map = new HashMap<>();
    int change(TreeNode root, int h){
        if(root==null) return -1;
        if(h%2 == 1){
            Stack<Integer> n = map.getOrDefault(h,new Stack<>());
            n.add(root.val);
            map.put(h,n);
        }
        change(root.left, h+1);
        change(root.right, h+1);
        return ans=h>ans?h:ans;
    }
    void exchange(TreeNode root, int h){
        if(root==null) return;
        if(h%2 == 1){
            Stack<Integer> n = map.get(h);
            root.val = n.pop();
        }
        exchange(root.left, h+1);
        exchange(root.right, h+1);
    }
    public TreeNode reverseOddLevels(TreeNode root) {
        change(root,0);
        exchange(root, 0);
        return root;
    }
}
class Solution1 {
    public TreeNode reverseOddLevels(TreeNode root) {
        dfs(root.left, root.right, true);
        return root;
    }

    public void dfs(TreeNode root1, TreeNode root2, boolean isOdd) {
        if (root1 == null) {
            return;
        }
        if (isOdd) {
            int temp = root1.val;
            root1.val = root2.val;
            root2.val = temp;
        }
        dfs(root1.left, root2.right, !isOdd);
        dfs(root1.right, root2.left, !isOdd);
    }
}